#include <stdio.h>
#include <stdlib.h>  
#include <math.h>
#include "projet.h"
#include "parser.h"
#include "algo1.h"
#include "cycle3.h"



/**
Fonction qui test si une arrête (i,j) appartient a un cycle de longueur 3.
**/
int appartient_cycle_3(int** liens,int nb_terminaux,int i,int j){
  int n;
  for(n=0;n<nb_terminaux;n++)
    if(n!=i&&n!=j&&liens[i][n]==1&&liens[j][n]==1)
      return 1;    
  return 0;   
}


/**
Fonction qui test si chaque arrêtes d'un graphe appartient a un cycle de longueur 3
**/
int verifie_cycle_3(int** liens,int nb_terminaux){
  int i;
  int j;
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      if(liens[i][j]==1&&appartient_cycle_3(liens,nb_terminaux,i,j)!=1)
	return 0;  
  return 1;
}

void relier_sommet_3(int** liens,int** distances,int nb_terminaux,int a,int b){
  int i;
  int j;
  int imin;
  int jmin;
  int min=-1;
  for(i=0;i<nb_terminaux;i++){
    if(i!=a&&i!=b&&liens[i][a]==1&&(min==-1||distances[i][b]<min)){
      min=distances[i][b];
      imin=i;
      jmin=b;
    }
    if(i!=a&&i!=b&&liens[i][b]==1&&(min==-1||distances[i][a]<min)){
      min=distances[i][a];
      imin=i;
      jmin=a;
    }
  }
  liens[imin][jmin] = 1;
  liens[jmin][imin] = 1;

} 



void creation_des_cycles_3(int** liens,int** distances,int nb_terminaux){
  int i;
  int j;
  int k;
  for(i=0;i<nb_terminaux;i++)
    for(j=0;j<nb_terminaux;j++)
      if(liens[i][j]==1&&appartient_cycle_3(liens,nb_terminaux,i,j)==0)
	relier_sommet_3(liens,distances,nb_terminaux,i,j);
}	
